home *** CD-ROM | disk | FTP | other *** search
/ CD Actual 85 / CD Temático 40 Febrero 2004.iso / DOS / ntfs / common / dir.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-02-11  |  26.5 KB  |  1,001 lines
  1. /*
  2.  *  dir.c
  3.  *
  4.  *  Copyright (C) 1995-1997, 1999 Martin von L÷wis
  5.  *  Copyright (C) 1999 Steve Dodd
  6.  *  Copyright (C) 1999 Joseph Malicki
  7.  */
  8.  
  9. #include "ntfstypes.h"
  10. #include "struct.h"
  11. #include "dir.h"
  12. #include "macros.h"
  13.  
  14. #include <errno.h>
  15. #include "super.h"
  16. #include "inode.h"
  17. #include "attr.h"
  18. #include "support.h"
  19. #include "util.h"
  20.  
  21. static char I30[]="$I30";
  22.  
  23. /* An index record should start with INDX, and the last word in each
  24.    block should contain the check value. If it passes, the original
  25.    values need to be restored */
  26. int ntfs_check_index_record(ntfs_inode *ino, char *record)
  27. {
  28.     return ntfs_fixup_record(ino->vol, record, "INDX", 
  29.                  ino->u.index.recordsize);
  30. }
  31.  
  32. static inline int ntfs_is_top(ntfs_u64 stack)
  33. {
  34.     return stack==14;
  35. }
  36.  
  37. static int ntfs_pop(ntfs_u64 *stack)
  38. {
  39.     static int width[16]={1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,-1};
  40.     int res=-1;
  41.     switch(width[*stack & 15])
  42.     {
  43.     case 1:res=(int)((*stack&15)>>1);
  44.         *stack>>=4;
  45.         break;
  46.     case 2:res=(int)(((*stack&63)>>2)+7);
  47.         *stack>>=6;
  48.         break;
  49.     case 3:res=(int)(((*stack & 255)>>3)+23);
  50.         *stack>>=8;
  51.         break;
  52.     case 4:res=(int)(((*stack & 1023)>>4)+55);
  53.         *stack>>=10;
  54.         break;
  55.     default:ntfs_error("Unknown encoding\n");
  56.     }
  57.     return res;
  58. }
  59.  
  60. static inline unsigned int ntfs_top(void)
  61. {
  62.     return 14;
  63. }
  64.  
  65. static ntfs_u64 ntfs_push(ntfs_u64 stack,int i)
  66. {
  67.     if(i<7)return (stack<<4)|(i<<1);
  68.     if(i<23)return (stack<<6)|((i-7)<<2)|1;
  69.     if(i<55)return (stack<<8)|((i-23)<<3)|3;
  70.     if(i<120)return (stack<<10)|((i-55)<<4)|7;
  71.     ntfs_error("Too many entries\n");
  72.     return ~((ntfs_u64)0);
  73. }
  74.  
  75. #if 0
  76. static void ntfs_display_stack(ntfs_u64 stack)
  77. {
  78.     while(!ntfs_is_top(stack))
  79.     {
  80.         printf("%d ",ntfs_pop(&stack));
  81.     }
  82.     printf("\n");
  83. }
  84. #endif
  85.  
  86. /* True if the entry points to another block of entries */
  87. static inline int ntfs_entry_has_subnodes(char* entry)
  88. {
  89.     return (int)NTFS_GETU8(entry+12)&1;
  90. }
  91.  
  92. /* True if it is not the 'end of dir' entry */
  93. static inline int ntfs_entry_is_used(char* entry)
  94. {
  95.     return (int)(NTFS_GETU8(entry+12)&2)==0;
  96. }
  97.  
  98. static int ntfs_allocate_index_block(ntfs_iterate_s *walk)
  99. {
  100.     ntfs_attribute *allocation=0,*bitmap=0;
  101.     int error,size,i,bit;
  102.     ntfs_u8 *bmap;
  103.     ntfs_io io;
  104.     ntfs_volume *vol=walk->dir->vol;
  105.  
  106.     /* check for allocation attribute */
  107.     allocation=ntfs_find_attr(walk->dir,vol->at_index_allocation,I30);
  108.     if(!allocation){
  109.         ntfs_u8 bmp[8];
  110.         /* create index allocation attribute */
  111.         error=ntfs_create_attr(walk->dir,vol->at_index_allocation,I30,
  112.                        0,0,&allocation);
  113.         if(error)return error;
  114.         ntfs_bzero(bmp,sizeof(bmp));
  115.         error=ntfs_create_attr(walk->dir,vol->at_bitmap,I30,
  116.                        bmp,sizeof(bmp),&bitmap);
  117.         if(error)return error;
  118.     }else
  119.         bitmap=ntfs_find_attr(walk->dir,vol->at_bitmap,I30);
  120.     if(!bitmap){
  121.         ntfs_error("Directory w/o bitmap\n");
  122.         return EINVAL;
  123.     }
  124.     size=bitmap->size;
  125.     bmap=ntfs_malloc(size);
  126.     if(!bmap)return ENOMEM;
  127.     io.fn_put=ntfs_put;
  128.     io.fn_get=ntfs_get;
  129.     io.param=bmap;
  130.     io.size=size;
  131.     error=ntfs_read_attr(walk->dir,vol->at_bitmap,I30,0,&io);
  132.     if(error){
  133.         ntfs_free(bmap);
  134.         return error;
  135.     }
  136.     if(io.size!=size){
  137.         ntfs_free(bmap);
  138.         return EIO;
  139.     }
  140.     
  141.     /* allocate a bit */
  142.     for(i=bit=0;i<size;i++){
  143.         if(bmap[i]==0xFF)continue;
  144.         for(bit=0;bit<8;bit++)
  145.             if(((bmap[i]>>bit) & 1) == 0)
  146.                 break;
  147.         if(bit!=8)break;
  148.     }
  149.     if(i==size)
  150.         /* FIXME: extend bitmap */
  151.         return EOPNOTSUPP;
  152.     walk->newblock=(i*8+bit)*walk->dir->u.index.clusters_per_record;
  153.     bmap[i]|= 1<<bit;
  154.     io.param=bmap;
  155.     io.size=size;
  156.     error=ntfs_write_attr(walk->dir,vol->at_bitmap,I30,0,&io);
  157.     if(error || io.size!=size){
  158.         ntfs_free(bmap);
  159.         return error?error:EIO;
  160.     }
  161.     ntfs_free(bmap);
  162.  
  163.     /* check whether record is out of allocated range */
  164.     size=allocation->size;
  165.     if(walk->newblock * vol->clustersize >= size){
  166.         /* build index record */
  167.         int s1=walk->dir->u.index.recordsize;
  168.         int nr_fix = s1/vol->blocksize+1;
  169.         int hsize;
  170.         char *record=ntfs_malloc(s1);
  171.         if( !record )
  172.             return ENOMEM;
  173.         ntfs_bzero(record,s1);
  174.         /* magic */
  175.         ntfs_memcpy(record,"INDX",4);
  176.         /* offset to fixups */
  177.         NTFS_PUTU16(record+4,0x28);
  178.         /* number of fixups */
  179.         NTFS_PUTU16(record+6,nr_fix);
  180.         /* FIXME: log file number */
  181.         /* VCN of buffer */
  182.         NTFS_PUTU64(record+0x10,walk->newblock);
  183.         /* header size. */
  184.         hsize = 0x10+2*nr_fix;
  185.         hsize = (hsize+7) & ~7; /* Align. */
  186.         NTFS_PUTU16(record+0x18, hsize);
  187.         /* total size of record */
  188.         NTFS_PUTU32(record+0x20,s1-0x18);
  189.         /* Writing the data will extend the attribute. */
  190.         io.param=record;
  191.         io.size=s1;
  192.         io.do_read=0;
  193.         error=ntfs_readwrite_attr(walk->dir, allocation, size, &io);
  194.         if(error || io.size!=s1){
  195.             ntfs_free(record);
  196.             return error?error:EIO;
  197.         }
  198.         ntfs_free(record);
  199.     }
  200.  
  201.     return 0;
  202. }
  203.  
  204. /* Write an index block (root or allocation) back to storage.
  205.    used is the total number of bytes in buf, including all headers. */
  206.  
  207. static int ntfs_index_writeback(ntfs_iterate_s *walk, ntfs_u8 *buf, int block,
  208.                 int used)
  209. {
  210.     ntfs_io io;
  211.     int error;
  212.     ntfs_attribute *a;
  213.     ntfs_volume *vol = walk->dir->vol;
  214.     
  215.     io.fn_put=0;
  216.     io.fn_get=ntfs_get;
  217.     io.param=buf;
  218.     if(block==-1){
  219.         NTFS_PUTU16(buf+0x14,used-0x10);
  220.         /* 0x18 is a copy thereof */
  221.         NTFS_PUTU16(buf+0x18,used-0x10);
  222.         io.size=used;
  223.         error=ntfs_write_attr(walk->dir,vol->at_index_root,
  224.                       I30,0,&io);
  225.         if(error)return error;
  226.         if(io.size!=used)return EIO;
  227.         /* shrink if necessary */
  228.         a = ntfs_find_attr(walk->dir, vol->at_index_root, I30);
  229.         ntfs_resize_attr(walk->dir, a, used);
  230.     }else{
  231.         NTFS_PUTU16(buf+0x1C,used-0x18);
  232.         ntfs_insert_fixups(buf,vol->blocksize);
  233.         io.size=walk->dir->u.index.recordsize;
  234.         error=ntfs_write_attr(walk->dir,vol->at_index_allocation,I30,
  235.                       block*vol->clustersize,
  236.                       &io);
  237.         if(error)return error;
  238.         if(io.size!=walk->dir->u.index.recordsize)
  239.             return EIO;
  240.     }
  241.     return 0;
  242. }
  243.  
  244. static int ntfs_split_record(ntfs_iterate_s *walk, char *start, int bsize,
  245.     int usize)
  246. {
  247.     char *entry,*prev;
  248.     ntfs_u8 *newbuf=0,*middle=0;
  249.     int error,othersize,mlen;
  250.     ntfs_io io;
  251.     ntfs_volume *vol=walk->dir->vol;
  252.     int oldblock;
  253.  
  254.     error=ntfs_allocate_index_block(walk);
  255.     if(error)
  256.         return error;
  257.     /* This should not happen */
  258.     if(walk->block == -1){
  259.         ntfs_error("Trying to split root");
  260.         return EOPNOTSUPP;
  261.     }
  262.     entry = start+NTFS_GETU16(start+0x18)+0x18; 
  263.     for(prev=entry; entry-start<usize/2; entry += NTFS_GETU16(entry+8))
  264.         prev=entry;
  265.  
  266.     newbuf=ntfs_malloc(vol->index_recordsize);
  267.     if(!newbuf)
  268.         return ENOMEM;
  269.     io.fn_put=ntfs_put;
  270.     io.fn_get=ntfs_get;
  271.     io.param=newbuf;
  272.     io.size=vol->index_recordsize;
  273.     /* read in old header. FIXME: reading everything is overkill */
  274.     error=ntfs_read_attr(walk->dir,vol->at_index_allocation,I30,
  275.                  walk->newblock*vol->clustersize,&io);
  276.     if(error)goto out;
  277.     if(io.size!=vol->index_recordsize){
  278.         error=EIO;
  279.         goto out;
  280.     }
  281.     /* FIXME: adjust header */
  282.     /* copy everything from entry to new block */
  283.     othersize=usize-(entry-start);
  284.     ntfs_memcpy(newbuf+NTFS_GETU16(newbuf+0x18)+0x18,entry,othersize);
  285.     /* Copy flags. */
  286.     NTFS_PUTU32(newbuf+0x24, NTFS_GETU32(start+0x24));
  287.     error=ntfs_index_writeback(walk,newbuf,walk->newblock,
  288.                    othersize+NTFS_GETU16(newbuf+0x18)+0x18);
  289.     if(error)goto out;
  290.  
  291.     /* move prev to walk */
  292.     mlen=NTFS_GETU16(prev+0x8);
  293.     /* Remember old child node. */
  294.     if(ntfs_entry_has_subnodes(prev))
  295.         oldblock = NTFS_GETU32(prev+mlen-8);
  296.     else
  297.         oldblock = -1;
  298.     /* allow for pointer to subnode */
  299.     middle=ntfs_malloc(ntfs_entry_has_subnodes(prev)?mlen:mlen+8);
  300.     if(!middle){
  301.         error=ENOMEM;
  302.         goto out;
  303.     }
  304.     ntfs_memcpy(middle,prev,mlen);
  305.     /* set has_subnodes flag */
  306.     NTFS_PUTU8(middle+0xC, NTFS_GETU8(middle+0xC) | 1);
  307.     /* middle entry points to block, parent entry will point to newblock */
  308.     NTFS_PUTU64(middle+mlen-8,walk->block);
  309.     if(walk->new_entry)
  310.         ntfs_error("entry not reset");
  311.     walk->new_entry=middle;
  312.     walk->u.flags|=ITERATE_SPLIT_DONE;
  313.     /* Terminate old block. */
  314.     othersize = usize-(prev-start);
  315.     NTFS_PUTU64(prev, 0);
  316.     if(oldblock==-1){
  317.         NTFS_PUTU32(prev+8, 0x10);
  318.         NTFS_PUTU32(prev+0xC, 2);
  319.         othersize += 0x10;
  320.     }else{
  321.         NTFS_PUTU32(prev+8, 0x18);
  322.         NTFS_PUTU32(prev+0xC, 3);
  323.         NTFS_PUTU64(prev+0x10, oldblock);
  324.         othersize += 0x18;
  325.     }
  326.     /* write back original block */
  327.     error=ntfs_index_writeback(walk,start,walk->block,othersize);
  328.  out:
  329.     if(newbuf)ntfs_free(newbuf);
  330.     if(middle)ntfs_free(middle);
  331.     return error;
  332. }
  333.  
  334. static int ntfs_dir_insert(ntfs_iterate_s *walk, char *start, char* entry)
  335. {
  336.     int blocksize,usedsize,error,offset;
  337.     int do_split=0;
  338.     offset=entry-start;
  339.     if(walk->block==-1){ /*index root */
  340.         blocksize=walk->dir->vol->mft_recordsize;
  341.         usedsize=NTFS_GETU16(start+0x14)+0x10;
  342.     }else{
  343.         blocksize=walk->dir->u.index.recordsize;
  344.         usedsize=NTFS_GETU16(start+0x1C)+0x18;
  345.     }
  346.     if(usedsize+walk->new_entry_size > blocksize){
  347.         char* s1=ntfs_malloc(blocksize+walk->new_entry_size);
  348.         if(!s1)return ENOMEM;
  349.         ntfs_memcpy(s1,start,usedsize);
  350.         do_split=1;
  351.         /* adjust entry to s1 */
  352.         entry=s1+(entry-start);
  353.         start=s1;
  354.     }
  355.     ntfs_memmove(entry+walk->new_entry_size,entry,usedsize-offset);
  356.     ntfs_memcpy(entry,walk->new_entry,walk->new_entry_size);
  357.     usedsize+=walk->new_entry_size;
  358.     ntfs_free(walk->new_entry);
  359.     walk->new_entry=0;
  360.     if(do_split){
  361.         error=ntfs_split_record(walk,start,blocksize,usedsize);
  362.         ntfs_free(start);
  363.     }else{
  364.         error=ntfs_index_writeback(walk,start,walk->block,usedsize);
  365.         if(error)return error;
  366.     }
  367.     return 0;
  368. }
  369.  
  370. /* Try to split INDEX_ROOT attributes. Return E2BIG if nothing changed. */
  371.  
  372. int
  373. ntfs_split_indexroot(ntfs_inode *ino)
  374. {
  375.     ntfs_attribute *ra;
  376.     ntfs_u8 *root=0, *index=0;
  377.     ntfs_io io;
  378.     int error, off, i, bsize, isize;
  379.     ntfs_iterate_s walk;
  380.  
  381.     ra = ntfs_find_attr(ino, ino->vol->at_index_root, I30);
  382.     if(!ra)
  383.         return E2BIG;
  384.     bsize = ino->vol->mft_recordsize;
  385.     root = ntfs_malloc(bsize);
  386.     if(!root)
  387.         return E2BIG;
  388.     io.fn_put = ntfs_put;
  389.     io.param = root;
  390.     io.size = bsize;
  391.     error = ntfs_read_attr(ino, ino->vol->at_index_root, I30, 0, &io);
  392.     if(error)
  393.         goto out;
  394.     off = 0x20;
  395.     /* Count number of entries. */
  396.     for(i = 0; ntfs_entry_is_used(root+off); i++)
  397.         off += NTFS_GETU16(root+off+8);
  398.     if(i<=2){
  399.         /* We don't split small index roots. */
  400.         error = E2BIG;
  401.         goto out;
  402.     }
  403.     index = ntfs_malloc(ino->vol->index_recordsize);
  404.     if(!index) {
  405.         error = ENOMEM; goto out;
  406.     }
  407.     walk.dir = ino;
  408.     walk.block = -1;
  409.     walk.result = walk.new_entry = 0;
  410.     walk.name = 0;
  411.     error = ntfs_allocate_index_block(&walk);
  412.     if(error)
  413.         goto out;
  414.  
  415.     /* Write old root to new index block. */
  416.     io.param = index;
  417.     io.size = ino->vol->index_recordsize;
  418.     error = ntfs_read_attr(ino, ino->vol->at_index_allocation, I30,
  419.                    walk.newblock*ino->vol->clustersize, &io);
  420.     if(error)
  421.         goto out;
  422.     isize = NTFS_GETU16(root+0x18) - 0x10;
  423.     ntfs_memcpy(index+NTFS_GETU16(index+0x18)+0x18, root+0x20, isize);
  424.     /* Copy flags. */
  425.     NTFS_PUTU32(index+0x24, NTFS_GETU32(root+0x1C));
  426.  
  427.     error = ntfs_index_writeback(&walk, index, walk.newblock, 
  428.                      isize+NTFS_GETU16(index+0x18)+0x18);
  429.     if(error)
  430.         goto out;
  431.  
  432.     /* Mark root as split. */
  433.     NTFS_PUTU32(root+0x1C, 1);
  434.     /* Truncate index root. */
  435.     NTFS_PUTU64(root+0x20, 0);
  436.     NTFS_PUTU32(root+0x28, 0x18);
  437.     NTFS_PUTU32(root+0x2C, 3);
  438.     NTFS_PUTU64(root+0x30, walk.newblock);
  439.     error = ntfs_index_writeback(&walk,root,-1,0x38);
  440.  out:
  441.     ntfs_free(root);
  442.     ntfs_free(index);
  443.     return error;
  444. }
  445.  
  446. /* The entry has been found. Copy the result in the caller's buffer */
  447. static int ntfs_copyresult(char *dest,char *source)
  448. {
  449.     int length=NTFS_GETU16(source+8);
  450.     ntfs_memcpy(dest,source,length);
  451.     return 1;
  452. }
  453.  
  454. /* use $UpCase some day */
  455. static inline unsigned short ntfs_my_toupper(ntfs_volume *vol, ntfs_u16 x)
  456. {
  457.     /* we should read any pending rest of $UpCase here */
  458.     if(x >= vol->upcase_length)
  459.         return x;
  460.     return vol->upcase[x];
  461. }
  462.  
  463. /* everything passed in walk and entry */
  464. static int ntfs_my_strcmp(ntfs_iterate_s *walk, const unsigned char *entry)
  465. {
  466.     int lu=*(entry+0x50);
  467.     int i;
  468.  
  469.     ntfs_u16* name=(ntfs_u16*)(entry+0x52);
  470.     ntfs_volume *vol=walk->dir->vol;
  471.     for(i=0;i<lu && i<walk->namelen;i++)
  472.         if(ntfs_my_toupper(vol,NTFS_GETU16(name+i))!=ntfs_my_toupper(vol,NTFS_GETU16(walk->name+i)))
  473.             break;
  474.     if(i==lu && i==walk->namelen)return 0;
  475.     if(i==lu)return 1;
  476.     if(i==walk->namelen)return -1;
  477.     if(ntfs_my_toupper(vol,NTFS_GETU16(name+i))<ntfs_my_toupper(vol,NTFS_GETU16(walk->name+i)))return 1;
  478.     return -1;
  479. }
  480.  
  481. /* Necessary forward declaration */
  482. static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry);
  483.  
  484. /* Parse a block of entries. Load the block, fix it up, and iterate
  485.    over the entries. The block is given as virtual cluster number */
  486. static int ntfs_getdir_record(ntfs_iterate_s *walk, int block)
  487. {
  488.     int length=walk->dir->u.index.recordsize;
  489.     char *record=(char*)ntfs_malloc(length);
  490.     char *offset;
  491.     int retval,error;
  492.     int oldblock;
  493.     ntfs_io io;
  494.  
  495.     if( !record )
  496.         return ENOMEM;
  497.  
  498.     io.fn_put=ntfs_put;
  499.     io.param=record;
  500.     io.size=length;
  501.     /* Read the block from the index allocation attribute */
  502.     error=ntfs_read_attr(walk->dir,walk->dir->vol->at_index_allocation,I30,
  503.                  block*walk->dir->vol->clustersize,&io);
  504.     if(error || io.size!=length){
  505.         ntfs_error("read failed\n");
  506.         ntfs_free(record);
  507.         return 0;
  508.     }
  509.     if(!ntfs_check_index_record(walk->dir,record)){
  510.         ntfs_error("%x is not an index record\n",block);
  511.         ntfs_free(record);
  512.         return 0;
  513.     }
  514.     offset=record+NTFS_GETU16(record+0x18)+0x18;
  515.     oldblock=walk->block;
  516.     walk->block=block;
  517.     retval=ntfs_getdir_iterate(walk,record,offset);
  518.     walk->block=oldblock;
  519.     ntfs_free(record);
  520.     return retval;
  521. }
  522.  
  523. /* go down to the next block of entries. These collate before
  524.    the current entry */
  525. static int ntfs_descend(ntfs_iterate_s *walk, ntfs_u8 *start, ntfs_u8 *entry)
  526. {
  527.     int length=NTFS_GETU16(entry+8);
  528.     int nextblock=NTFS_GETU32(entry+length-8);
  529.     int error;
  530.  
  531.     if(!ntfs_entry_has_subnodes(entry)) {
  532.         ntfs_error("illegal ntfs_descend call\n");
  533.         return 0;
  534.     }
  535.     error=ntfs_getdir_record(walk,nextblock);
  536.     if(!error && walk->type==DIR_INSERT && 
  537.        (walk->u.flags & ITERATE_SPLIT_DONE)){
  538.         /* Split has occurred. Adjust entry, insert new_entry. */
  539.         NTFS_PUTU32(entry+length-8,walk->newblock);
  540.         /* Reset flags, as the current block might be split again. */
  541.         walk->u.flags &= ~ITERATE_SPLIT_DONE;
  542.         error=ntfs_dir_insert(walk,start,entry);
  543.     }
  544.     return error;
  545. }
  546.  
  547. static int 
  548. ntfs_getdir_iterate_byposition(ntfs_iterate_s *walk,char* start,char *entry)
  549. {
  550.     int retval=0;
  551.     int curpos=0,destpos=0;
  552.     int length;
  553.     if(walk->u.pos!=0){
  554.         if(ntfs_is_top(walk->u.pos))return 0;
  555.         destpos=ntfs_pop(&walk->u.pos);
  556.     }
  557.     while(1){
  558.         if(walk->u.pos==0)
  559.         {
  560.             if(ntfs_entry_has_subnodes(entry))
  561.                 ntfs_descend(walk,start,entry);
  562.             else
  563.                 walk->u.pos=ntfs_top();
  564.             if(ntfs_is_top(walk->u.pos) && !ntfs_entry_is_used(entry))
  565.             {
  566.                 return 1;
  567.             }
  568.             walk->u.pos=ntfs_push(walk->u.pos,curpos);
  569.             return 1;
  570.         }
  571.         if(curpos==destpos)
  572.         {
  573.             if(!ntfs_is_top(walk->u.pos) && ntfs_entry_has_subnodes(entry))
  574.             {
  575.                 retval=ntfs_descend(walk,start,entry);
  576.                 if(retval){
  577.                     walk->u.pos=ntfs_push(walk->u.pos,curpos);
  578.                     return retval;
  579.                 }else{
  580.                     if(!ntfs_entry_is_used(entry))
  581.                         return 0;
  582.                     walk->u.pos=0;
  583.                 }
  584.             }
  585.             if(ntfs_entry_is_used(entry))
  586.             {
  587.                 retval=ntfs_copyresult(walk->result,entry);
  588.                 walk->u.pos=0;
  589.             }else{
  590.                 walk->u.pos=ntfs_top();
  591.                 return 0;
  592.             }
  593.         }
  594.         curpos++;
  595.         if(!ntfs_entry_is_used(entry))break;
  596.         length=NTFS_GETU16(entry+8);
  597.         if(!length){
  598.             ntfs_error("infinite loop\n");
  599.             break;
  600.         }
  601.         entry+=length;
  602.     }
  603.     return -1;
  604. }
  605.     
  606. /* Iterate over a list of entries, either from an index block, or from
  607.    the index root. 
  608.    If searching BY_POSITION, pop the top index from the position. If the
  609.    position stack is empty then, return the item at the index and set the
  610.    position to the next entry. If the position stack is not empty, 
  611.    recursively proceed for subnodes. If the entry at the position is the
  612.    'end of dir' entry, return 'not found' and the empty stack.
  613.    If searching BY_NAME, walk through the items until found or until
  614.    one item is collated after the requested item. In the former case, return
  615.    the result. In the latter case, recursively proceed to the subnodes.
  616.    If 'end of dir' is reached, the name is not in the directory */
  617. static int ntfs_getdir_iterate(ntfs_iterate_s *walk, char *start, char *entry)
  618. {
  619.     int length;
  620.     int cmp;
  621.  
  622.     if(walk->type==BY_POSITION)
  623.         return ntfs_getdir_iterate_byposition(walk,start,entry);
  624.     do{
  625.         /* if the current entry is a real one, compare with the
  626.            requested item. If the current entry is the last item,
  627.            it is always larger than the requested item */
  628.         cmp = ntfs_entry_is_used(entry) ? ntfs_my_strcmp(walk,entry) : -1;
  629.         switch(walk->type){
  630.         case BY_NAME:
  631.             switch(cmp)
  632.             {
  633.             case -1:return ntfs_entry_has_subnodes(entry)?
  634.                        ntfs_descend(walk,start,entry):0;
  635.             case  0:return ntfs_copyresult(walk->result,entry);
  636.             case  1:break;
  637.             }
  638.             break;
  639.         case DIR_INSERT:
  640.             switch(cmp){
  641.             case -1:return ntfs_entry_has_subnodes(entry)?
  642.                        ntfs_descend(walk,start,entry):
  643.                            ntfs_dir_insert(walk,start,entry);
  644.             case  0:return EEXIST;
  645.             case  1:break;
  646.             }
  647.             break;
  648.         default:
  649.             ntfs_error("TODO\n");
  650.         }
  651.         if(!ntfs_entry_is_used(entry))break;
  652.         length=NTFS_GETU16(entry+8);
  653.         if(!length){
  654.             ntfs_error("infinite loop\n");
  655.             break;
  656.         }
  657.         entry+=length;
  658.     }while(1);
  659.     return 0;
  660. }
  661.  
  662. /*      Tree walking is done using position numbers. The following numbers have
  663.     a special meaning:
  664.     0    start (.)
  665.     -1   no more entries
  666.     -2   ..
  667.     All other numbers encode sequences of indices. The sequence a,b,c is 
  668.     encoded as <stop><c><b><a>, where <foo> is the encoding of foo. The
  669.     first few integers are encoded as follows:
  670.     0:    0000    1:    0010    2:    0100    3:    0110
  671.     4:    1000    5:    1010    6:    1100 stop:    1110
  672.     7:  000001    8:  000101        9:  001001   10:  001101
  673.     The least significant bits give the width of this encoding, the
  674.     other bits encode the value, starting from the first value of the 
  675.     interval.
  676.      tag     width  first value  last value
  677.      0       3      0            6
  678.      01      4      7            22
  679.      011     5      23           54
  680.      0111    6      55           119
  681.      More values are hopefully not needed, as the file position has currently
  682.      64 bits in total.
  683. */
  684.  
  685. /* Find an entry in the directory. Return 0 if not found, otherwise copy
  686.    the entry to the result buffer. */
  687. int ntfs_getdir(ntfs_iterate_s* walk)
  688. {
  689.     int length=walk->dir->vol->mft_recordsize;
  690.     int retval,error;
  691.     /* start at the index root.*/
  692.     char *root=ntfs_malloc(length);
  693.     ntfs_io io;
  694.  
  695.     if( !root )
  696.         return ENOMEM;
  697.  
  698.     io.fn_put=ntfs_put;
  699.     io.param=root;
  700.     io.size=length;
  701.     error=ntfs_read_attr(walk->dir,walk->dir->vol->at_index_root,
  702.                  I30,0,&io);
  703.     if(error)
  704.     {
  705.         ntfs_error("Not a directory\n");
  706.         return 0;
  707.     }
  708.     walk->block=-1;
  709.     /* FIXME: move these to walk */
  710.     walk->dir->u.index.recordsize = NTFS_GETU32(root+0x8);
  711.     walk->dir->u.index.clusters_per_record = NTFS_GETU32(root+0xC);
  712.     /* FIXME: consistency check */
  713.     /* skip header */
  714.     retval = ntfs_getdir_iterate(walk,root,root+0x20);
  715.     ntfs_free(root);
  716.     return retval;
  717. }
  718.  
  719. /* Find an entry in the directory by its position stack. Iteration starts
  720.    if the stack is 0, in which case the position is set to the first item
  721.    in the directory. If the position is nonzero, return the item at the
  722.    position and change the position to the next item. The position is -1
  723.    if there are no more items */
  724. int ntfs_getdir_byposition(ntfs_iterate_s *walk)
  725. {
  726.     walk->type=BY_POSITION;
  727.     return ntfs_getdir(walk);
  728. }
  729.  
  730. /* Find an entry in the directory by its name. Return 0 if not found */
  731. int ntfs_getdir_byname(ntfs_iterate_s *walk)
  732. {
  733.     walk->type=BY_NAME;
  734.     return ntfs_getdir(walk);
  735. }
  736.  
  737. int ntfs_getdir_unsorted(ntfs_inode *ino,ntfs_u32 *p_high,ntfs_u32* p_low,
  738.              int(*cb)(ntfs_u8*,void*),void *param)
  739. {
  740.     char *buf=0,*entry=0;
  741.     ntfs_io io;
  742.     int length;
  743.     int block;
  744.     int start;
  745.     ntfs_attribute *attr;
  746.     ntfs_volume *vol=ino->vol;
  747.     int byte,bit;
  748.     int error=0;
  749.  
  750.     if(!ino){
  751.         ntfs_error("No inode passed to getdir_unsorted\n");
  752.         return EINVAL;
  753.     }
  754.     if(!vol){
  755.         ntfs_error("Inode %d has no volume\n",ino->i_number);
  756.         return EINVAL;
  757.     }
  758.     ntfs_debug(DEBUG_DIR3,"unsorted 1\n");
  759.     /* are we still in the index root */
  760.     if(*p_high==0){
  761.         buf=ntfs_malloc(length=vol->mft_recordsize);
  762.         if( !buf )
  763.             return ENOMEM;
  764.         io.fn_put=ntfs_put;
  765.         io.param=buf;
  766.         io.size=length;
  767.         error=ntfs_read_attr(ino,vol->at_index_root,I30,0,&io);
  768.         if(error){
  769.             ntfs_free(buf);
  770.             return error;
  771.         }
  772.         ino->u.index.recordsize = NTFS_GETU32(buf+0x8);
  773.         ino->u.index.clusters_per_record = NTFS_GETU32(buf+0xC);
  774.         entry=buf+0x20;
  775.         ntfs_debug(DEBUG_DIR3,"unsorted 2\n");
  776.     }else{ /* we are in an index record */
  777.         length=ino->u.index.recordsize;
  778.         buf=ntfs_malloc(length);
  779.         if( !buf )
  780.             return ENOMEM;
  781.         io.fn_put=ntfs_put;
  782.         io.param=buf;
  783.         io.size=length;
  784.         /* 0 is index root, index allocation starts with 4 */
  785.         block = *p_high - ino->u.index.clusters_per_record;
  786.         error=ntfs_read_attr(ino,vol->at_index_allocation,I30,
  787.                      block*vol->clustersize,&io);
  788.         if(!error && io.size!=length)error=EIO;
  789.         if(error){
  790.             ntfs_error("read failed\n");
  791.             ntfs_free(buf);
  792.             return error;
  793.         }
  794.         if(!ntfs_check_index_record(ino,buf)){
  795.             ntfs_error("%x is not an index record\n",block);
  796.             ntfs_free(buf);
  797.             return ENOTDIR;
  798.         }
  799.         entry=buf+NTFS_GETU16(buf+0x18)+0x18;
  800.         ntfs_debug(DEBUG_DIR3,"unsorted 3\n");
  801.     }
  802.  
  803.     /* process the entries */
  804.     start=*p_low;
  805.     while(ntfs_entry_is_used(entry)){
  806.         ntfs_debug(DEBUG_DIR3,"unsorted 4\n");
  807.         if(start)
  808.             start--; /* skip entries that were already processed */
  809.         else{
  810.             ntfs_debug(DEBUG_DIR3,"unsorted 5\n");
  811.             if((error=cb(entry,param)))
  812.                 /* the entry could not be processed */
  813.                 break;
  814.             (*p_low)++;
  815.         }
  816.         entry+=NTFS_GETU16(entry+8);
  817.     }
  818.  
  819.     ntfs_debug(DEBUG_DIR3,"unsorted 6\n");
  820.     /* caller did not process all entries */
  821.     if(error){
  822.         ntfs_free(buf);
  823.         ntfs_debug(DEBUG_DIR3,"unsorted 7\n");
  824.         return error;
  825.     }
  826.  
  827.     /* we have to locate the next record */
  828.     ntfs_free(buf);
  829.     buf=0;
  830.     *p_low=0;
  831.     attr=ntfs_find_attr(ino,vol->at_bitmap,I30);
  832.     if(!attr){
  833.         /* directory does not have index allocation */
  834.         *p_high=0xFFFFFFFF;
  835.         *p_low=0;
  836.         ntfs_debug(DEBUG_DIR3,"unsorted 8\n");
  837.         return 0;
  838.     }
  839.     buf=ntfs_malloc(length=attr->size);
  840.     if( !buf )
  841.         return ENOMEM;
  842.  
  843.     io.param=buf;
  844.     io.size=length;
  845.     error=ntfs_read_attr(ino,vol->at_bitmap,I30,0,&io);
  846.     if(!error && io.size!=length)error=EIO;
  847.     if(error){
  848.         ntfs_free(buf);
  849.         ntfs_debug(DEBUG_DIR3,"unsorted 9\n");
  850.         return EIO;
  851.     }
  852.     attr=ntfs_find_attr(ino,vol->at_index_allocation,I30);
  853.     while(1){
  854.         if(*p_high*vol->clustersize > attr->size){
  855.             /* no more index records */
  856.             *p_high=0xFFFFFFFF;
  857.             ntfs_free(buf);
  858.             ntfs_debug(DEBUG_DIR3,"unsorted 10\n");
  859.             return 0;
  860.         }
  861.         *p_high+=ino->u.index.clusters_per_record;
  862.         byte=*p_high/ino->u.index.clusters_per_record-1;
  863.         bit  = 1 << (byte & 7);
  864.         byte = byte >> 3;
  865.         /* this record is allocated */
  866.         if(buf[byte] & bit)
  867.             break;
  868.     }
  869.     ntfs_debug(DEBUG_DIR3,"unsorted 11\n");
  870.     ntfs_free(buf);
  871.     return 0;
  872. }
  873.  
  874. int ntfs_dir_add(ntfs_inode *dir, ntfs_inode *new, ntfs_attribute *name)
  875. {
  876.     ntfs_iterate_s walk;
  877.     int nsize,esize;
  878.     ntfs_u8* entry,*ndata;
  879.     int error;
  880.  
  881.     walk.type=DIR_INSERT;
  882.     walk.dir=dir;
  883.     walk.u.flags=0;
  884.     nsize = name->size;
  885.     ndata = name->d.data;
  886.     walk.name=(ntfs_u16*)(ndata+0x42);
  887.     walk.namelen=NTFS_GETU8(ndata+0x40);
  888.     walk.new_entry_size = esize = ((nsize+0x18)/8)*8;
  889.     walk.new_entry=entry=ntfs_malloc(esize);
  890.     if(!entry)return ENOMEM;
  891.     ntfs_bzero(entry,esize);
  892.     NTFS_PUTINUM(entry,new);
  893.     NTFS_PUTU16(entry+0x8,esize); /* size of entry */
  894.     NTFS_PUTU16(entry+0xA,nsize); /* size of original name attribute */
  895.     NTFS_PUTU32(entry+0xC,0);     /* FIXME: D-F? */
  896.     ntfs_memcpy(entry+0x10,ndata,nsize);
  897.     error=ntfs_getdir(&walk);
  898.     if(walk.new_entry)
  899.         ntfs_free(walk.new_entry);
  900.     return error;
  901. }
  902.  
  903. #if 0
  904. int ntfs_dir_add1(ntfs_inode *dir,const char* name,int namelen,ntfs_inode *ino)
  905. {
  906.     ntfs_iterate_s walk;
  907.     int error;
  908.     int nsize;
  909.     char *entry;
  910.     ntfs_attribute *name_attr;
  911.     error=ntfs_decodeuni(dir->vol,name,namelen,&walk.name,&walk.namelen);
  912.     if(error)
  913.         return error;
  914.     /* FIXME: set flags */
  915.     walk.type=DIR_INSERT;
  916.     walk.dir=dir;
  917.     /*walk.new=ino;*/
  918.     /* prepare new entry */
  919.     /* round up to a multiple of 8 */
  920.     walk.new_entry_size = nsize = ((0x52+2*walk.namelen+7)/8)*8;
  921.     walk.new_entry=entry=ntfs_malloc(nsize);
  922.     if(!entry)
  923.         return ENOMEM;
  924.     ntfs_bzero(entry,nsize);
  925.     NTFS_PUTINUM(entry,ino);
  926.     NTFS_PUTU16(entry+8,nsize);
  927.     NTFS_PUTU16(entry+0xA,0x42+2*namelen); /*FIXME: size of name attr*/
  928.     NTFS_PUTU32(entry+0xC,0); /*FIXME: D-F? */
  929.     name_attr=ntfs_find_attr(ino,vol->at_file_name,0); /* FIXME:multiple names */
  930.     if(!name_attr || !name_attr->resident)
  931.         return EIDRM;
  932.     /* directory, file stamps, sizes, filename */
  933.     ntfs_memcpy(entry+0x10,name_attr->d.data,0x42+2*namelen);
  934.     error=ntfs_getdir(&walk);
  935.     ntfs_free(walk.name);
  936.     return error;
  937. }
  938. #endif
  939.  
  940. /* Fills out and creates an INDEX_ROOT attribute. */
  941.  
  942. int
  943. ntfs_add_index_root (ntfs_inode *ino, int type)
  944. {
  945.     ntfs_attribute *da;
  946.     ntfs_u8 data[0x30]; /* 0x20 header, 0x10 last entry */
  947.     char name[10];
  948.  
  949.     NTFS_PUTU32(data, type);
  950.     /* ??? */
  951.     NTFS_PUTU32(data+4, 1);
  952.     NTFS_PUTU32(data+8, ino->vol->index_recordsize);
  953.     NTFS_PUTU32(data+0xC, ino->vol->index_clusters_per_record);
  954.     /* ??? */
  955.     NTFS_PUTU32(data+0x10, 0x10);
  956.     /* Size of entries, including header. */
  957.     NTFS_PUTU32(data+0x14, 0x20);
  958.     NTFS_PUTU32(data+0x18, 0x20);
  959.     /* No index allocation, yet. */
  960.     NTFS_PUTU32(data+0x1C, 0);
  961.     /* add last entry. */
  962.     /* indexed MFT record. */
  963.     NTFS_PUTU64(data+0x20, 0);
  964.     /* size of entry */
  965.     NTFS_PUTU32(data+0x28, 0x10);
  966.     /* flags: last entry, no child nodes. */
  967.     NTFS_PUTU32(data+0x2C, 2);
  968.     /* compute name */
  969.     ntfs_indexname(name, type);
  970.     return ntfs_create_attr(ino, ino->vol->at_index_root, name,
  971.                 data, sizeof(data), &da);
  972. }
  973.  
  974. int
  975. ntfs_mkdir(ntfs_inode* dir,const char* name,int namelen, ntfs_inode *result)
  976. {
  977.     int error;
  978.     error = ntfs_alloc_inode(dir, result, name, namelen, NTFS_AFLAG_DIR);
  979.     if(error)
  980.         goto out;
  981.     error = ntfs_add_index_root(result, 0x30);
  982.     if (error)
  983.         goto out;
  984.     /* Set directory bit */
  985.     result->attr[0x16] |= 2;
  986.     error = ntfs_update_inode (dir);
  987.     if (error)
  988.         goto out;
  989.     error = ntfs_update_inode (result);
  990.     if (error)
  991.         goto out;
  992.  out:
  993.     return error;
  994. }
  995.  
  996. /*
  997.  * Local variables:
  998.  * c-file-style: "linux"
  999.  * End:
  1000.  */
  1001.